#include <stdio.h>
#include <stdlib.h>

/* 链表 */
typedef struct _Node
{
    int data;
    struct _Node *prev;
    struct _Node *next;
} Node;
typedef Node List;

void initList(List *list)
{
    list->prev = list;
    list->next = list;
}

void addFront(List *list, int data)
{
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = data;

    p->prev = list;
    p->next = list->next;
    list->next->prev = p;
    list->next = p;
}

void addBack(List *list, int data)
{
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = data;

    p->next = list;
    p->prev = list->prev;
    list->prev->next = p;
    list->prev = p;
}

void insertNode(Node *node, int data)
{
    addBack(node, data);
}

void insert(List *list, int index, int data)
{
    int n = 0;
    Node *p = list->next;
    while (n < index && p != list) {
        p = p->next;
        n++;
    }

    insertNode(p, data);
}

int get(List *list, int index)
{    
    int n = 0;
    Node *p = list->next;
    while (n < index && p != list) {
        p = p->next;
        n++;
    }
    return p->data;
}

void removeNode(Node *p)
{
    p->next->prev = p->prev;
    p->prev->next = p->next;
    free(p);
}

int isEmptyList(List *list)
{
    return list == list->next && list == list->prev;
}

int getListSize(List *list)
{
    int n = 0;
    for (Node *p = list->next; p != list; p = p->next) {
        n++;
    }
    return n;
}

void showList(List *list)
{
    printf("Size:%d Data:", getListSize(list));
    printf("[HEAD]");
    for (Node *p = list->next; p != list; p = p->next) {
        printf(" %d", p->data);
    }
    printf(" [TAIL]\n");
}

void showListR(List *list)
{
    printf("Size:%d Data:", getListSize(list));
    printf("[TAIL]");
    for (Node *p = list->prev; p != list; p = p->prev) {
        printf(" %d", p->data);
    }
    printf(" [HEAD]\n");
}

void removeList(List *list)
{
    while (!isEmptyList(list)) {
        removeNode(list->prev);
    }
}

Node* search(List *list, int data)
{
    for (Node *p = list->next; p != list; p = p->next) {
        if (p->data == data) {
            return p;
        }
    }
    return NULL;
}

Node* searchR(List *list, int data)
{
    for (Node *p = list->prev; p != list; p = p->prev) {
        if (p->data == data) {
            return p;
        }
    }
    return NULL;
}

void testList(void)
{
    List list;
    initList(&list);
    addBack(&list, 1);
    addBack(&list, 2);
    addBack(&list, 3);
    printf("list[%d]:%d\n", 2, get(&list, 2));
    printf("list[%d]:%d\n", 0, get(&list, 0));
    showList(&list);
    showListR(&list);
    removeList(&list);
    showList(&list);

    insert(&list, 0, 1);
    insert(&list, 0, 11);
    insert(&list, 0, 12);
    insert(&list, 1, 3);
    showList(&list);

    removeList(&list);
}

int main(int argc, char *argv[])
{
    testList();
    return 0;
}
